#include <iostream>
#include <unordered_map>
struct node{
	int _key;
	node* _next_node;
	node(int key,node* next_node){
		_key=key;
		_next_node=next_node;
	}
};
class LRUCache{
private:
	int m_nCapacity;
	node* dumy;
	std::unordered_map<int,int> has;
protected:
	void push_front(node*& pre,node*& cur){
			
		pre->_next_node=cur->_next_node;
		cur->_next_node=dumy->_next_node;
		dumy->_next_node=cur;
	}
	void pop_tail(){
		
		node* cur=dumy->_next_node;
		node* pre=dumy;
		while(cur && nullptr!=cur->_next_node){
			pre=cur;
			cur=cur->_next_node;
		}
		if(nullptr!=cur){
			has.erase(cur->_key);
		}
		pre->_next_node=nullptr;
	}	
public:	
	LRUCache(int capacity)
		:m_nCapacity(capacity){
			
		dumy=new node(-1,nullptr);
	}
	~LRUCache(){
		
		delete dumy;
	}

	
	int get(int key){
		
		if(!has.count(key)){
			return -1;
		}
		node* cur=dumy->_next_node;
		node* pre=dumy;
		while(cur && cur->_key!=key){
			pre=cur;
			cur=cur->_next_node;	
		}
		push_front(pre,cur);
		return has[key];
	}
	void put(int key,int value){
		
		if(get(key)!=-1){
			has[key]=value;
		}
		else{
			if(has.size()>m_nCapacity){
				pop_tail();
			}
			node* tmp=new node(key,dumy->_next_node);
			dumy->_next_node=tmp;
			has.insert({key,value});
		}
	}
};
